


/*-------------------------------------------------------------------------
 *
 * nodeIncrementalSort.c
 *	  处理关系增量排序的例程。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/executor/nodeIncrementalSort.c
 *
 * DESCRIPTION
 *
 *	增量排序是多关键字排序的一种优化变体，适用于输入已经按排序键的前缀排序的情况。
 *	例如，当请求按（key1，key2 ... keyN）排序时，如果输入已经按（key1，key2 ... keyM）排序，则可以
 *	将输入划分为键（key1，... keyM）相等的组，然后仅对其余列进行排序。
 *
 *	考虑以下示例。我们的输入元组由两个整数（X，Y）组成，已按X预排序，而要求按X和Y排序。让输入元组如下。
 *
 *	(1, 5)
 *	(1, 2)
 *	(2, 9)
 *	(2, 1)
 *	(2, 5)
 *	(3, 3)
 *	(3, 7)
 *
 *	增量排序算法将输入分为以下组，这些组具有相等的X，然后单独按Y排序：
 *
 *		(1, 5) (1, 2)
 *		(2, 9) (2, 1) (2, 5)
 *		(3, 3) (3, 7)
 *
 *	排序这些组并将它们放在一起后，我们将得到以下结果，该结果按X和Y排序，如请求的那样：
 *
 *	(1, 2)
 *	(1, 5)
 *	(2, 1)
 *	(2, 5)
 *	(2, 9)
 *	(3, 3)
 *	(3, 7)
 *
 *	增量排序比简单排序更有效，特别是在大型数据集上，因为它减少了必须一次排序的数据量，
 *	使其更有可能适合于work_mem（消除溢出到磁盘的需要）。但增量排序的主要优势在于它可以
 *	在排序整个数据集之前开始提前生成行，这对LIMIT的查询特别有利。
 *
 *	我们在这里实现的算法是在上述理论基础上修改的，通过两种不同的模式操作：
 *	  - 在安全的情况下，不检查前缀关键字组成员资格，提取最少数量的元组并对所有列进行排序。
 *	  - 提取单个前缀关键字组的所有元组，仅对未排序的列进行排序。
 *	我们总是以第一种模式开始，并使用启发式方法在认为有利时切换到第二种模式。
 *
 *	增量排序可以潜在地使用更少的内存，避免获取和排序数据集中的所有元组，并在整个结果集可用之前开始返回元组。
 *
 *	混合模式方法使我们能够优化非常小的组（新元组排序的开销高）和非常大的组（我们可以通过不在
 *	已排序列上进行排序来降低成本），尽管在模式切换时会产生一些额外成本。
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/htup_details.h"
#include "executor/execdebug.h"
#include "executor/nodeIncrementalSort.h"
#include "miscadmin.h"
#include "utils/lsyscache.h"
#include "utils/tuplesort.h"

/*
 * 我们需要在本地节点的排序信息或对于并行工作进程中存储仪表信息（这避免了在每次仪表调用时必须将信息从本地内存复制到共享内存）。
 * 此宏展开为选择适当的排序状态和组信息。
 *
 * 参数：
 * - node: 类型IncrementalSortState *
 * - groupName: 令牌fullsort或prefixsort
 */
#define INSTRUMENT_SORT_GROUP(node, groupName) \
	do { \
		if ((node)->ss.ps.instrument != NULL) \
		{ \
			if ((node)->shared_info && (node)->am_worker) \
			{ \
				Assert(IsParallelWorker()); \
				Assert(ParallelWorkerNumber <= (node)->shared_info->num_workers); \
				fc_instrumentSortedGroup(&(node)->shared_info->sinfo[ParallelWorkerNumber].groupName##GroupInfo, \
									  (node)->groupName##_state); \
			} \
			else \
			{ \
				fc_instrumentSortedGroup(&(node)->incsort_info.groupName##GroupInfo, \
									  (node)->groupName##_state); \
			} \
		} \
	} while (0)


/* ----------------------------------------------------------------
 * instrumentSortedGroup
 *
 * 因为增量排序处理（可能有很多）排序批次，我们需要在每次最终确定排序状态时捕获元组排序统计信息。
 * 此摘要数据稍后用于EXPLAIN ANALYZE输出。
 * ----------------------------------------------------------------
 */
static void fc_instrumentSortedGroup(IncrementalSortGroupInfo *fc_groupInfo,
					  Tuplesortstate *fc_sortState)
{
	TuplesortInstrumentation sort_instr;

	fc_groupInfo->groupCount++;

	tuplesort_get_stats(fc_sortState, &sort_instr);

	/* 计算使用的总内存和最大磁盘空间。 */
	switch (sort_instr.spaceType)
	{
		case SORT_SPACE_TYPE_DISK:
			fc_groupInfo->totalDiskSpaceUsed += sort_instr.spaceUsed;
			if (sort_instr.spaceUsed > fc_groupInfo->maxDiskSpaceUsed)
				fc_groupInfo->maxDiskSpaceUsed = sort_instr.spaceUsed;

			break;
		case SORT_SPACE_TYPE_MEMORY:
			fc_groupInfo->totalMemorySpaceUsed += sort_instr.spaceUsed;
			if (sort_instr.spaceUsed > fc_groupInfo->maxMemorySpaceUsed)
				fc_groupInfo->maxMemorySpaceUsed = sort_instr.spaceUsed;

			break;
	}

	/* 跟踪我们使用的每种排序方法。 */
	fc_groupInfo->sortMethods |= sort_instr.sortMethod;
}

/* ----------------------------------------------------------------
 * preparePresortedCols
 *
 * 准备有关预排序键比较的信息。
 * ----------------------------------------------------------------
 */
static void fc_preparePresortedCols(IncrementalSortState *fc_node)
{
	IncrementalSort *fc_plannode = castNode(IncrementalSort, fc_node->ss.ps.plan);

	fc_node->presorted_keys =
		(PresortedKeyData *) palloc(fc_plannode->nPresortedCols *
									sizeof(PresortedKeyData));

	/* 为每个预排序键预缓存比较函数。 */
	for (int fc_i = 0; fc_i < fc_plannode->nPresortedCols; fc_i++)
	{
		Oid			fc_equalityOp,
					fc_equalityFunc;
		PresortedKeyData *fc_key;

		fc_key = &fc_node->presorted_keys[fc_i];
		fc_key->attno = fc_plannode->sort.sortColIdx[fc_i];

		fc_equalityOp = get_equality_op_for_ordering_op(fc_plannode->sort.sortOperators[fc_i],
													 NULL);
		if (!OidIsValid(fc_equalityOp))
			elog(ERROR, "missing equality operator for ordering operator %u",
				 fc_plannode->sort.sortOperators[fc_i]);

		fc_equalityFunc = get_opcode(fc_equalityOp);
		if (!OidIsValid(fc_equalityFunc))
			elog(ERROR, "missing function for operator %u", fc_equalityOp);

		/* 查找比较函数 */
		fmgr_info_cxt(fc_equalityFunc, &fc_key->flinfo, CurrentMemoryContext);

		/* 我们可以只初始化一次调用信息并重用它 */
		fc_key->fcinfo = palloc0(SizeForFunctionCallInfo(2));
		InitFunctionCallInfoData(*fc_key->fcinfo, &fc_key->flinfo, 2,
								 fc_plannode->sort.collations[fc_i], NULL, NULL);
		fc_key->fcinfo->args[0].isnull = false;
		fc_key->fcinfo->args[1].isnull = false;
	}
}

/* ----------------------------------------------------------------
 * isCurrentGroup
 *
 * 通过将预排序列值与当前组的枢轴元组进行比较，检查给定元组是否属于当前排序组。
 * ----------------------------------------------------------------
 */
static bool fc_isCurrentGroup(IncrementalSortState *fc_node, TupleTableSlot *fc_pivot, TupleTableSlot *fc_tuple)
{
	int			fc_nPresortedCols;

	fc_nPresortedCols = castNode(IncrementalSort, fc_node->ss.ps.plan)->nPresortedCols;

	/*
	 * 输入按键*（0，... n）排序意味着尾部键更 likely改变。因此我们从最后一个预排序列开始进行比较，以优化不平等的早期检测并最小化函数调用数量。
	 */
	for (int fc_i = fc_nPresortedCols - 1; fc_i >= 0; fc_i--)
	{
		Datum		fc_datumA,
					fc_datumB,
					fc_result;
		bool		fc_isnullA,
					fc_isnullB;
		AttrNumber	fc_attno = fc_node->presorted_keys[fc_i].attno;
		PresortedKeyData *fc_key;

		fc_datumA = slot_getattr(fc_pivot, fc_attno, &fc_isnullA);
		fc_datumB = slot_getattr(fc_tuple, fc_attno, &fc_isnullB);

		/* NULL与NULL的特例，否则使用标准比较 */
		if (fc_isnullA || fc_isnullB)
		{
			if (fc_isnullA == fc_isnullB)
				continue;
			else
				return false;
		}

		fc_key = &fc_node->presorted_keys[fc_i];

		fc_key->fcinfo->args[0].value = fc_datumA;
		fc_key->fcinfo->args[1].value = fc_datumB;

		/* 只是为了以防万一，我们每次都重置 isnull */
		fc_key->fcinfo->isnull = false;

		fc_result = FunctionCallInvoke(fc_key->fcinfo);

		/* 检查结果是否为 null，因为调用者显然不期望出现这种情况 */
		if (fc_key->fcinfo->isnull)
			elog(ERROR, "function %u returned NULL", fc_key->flinfo.fn_oid);

		if (!DatumGetBool(fc_result))
			return false;
	}
	return true;
}


/* ----------------------------------------------------------------
 * switchToPresortedPrefixMode
 *
 * 当我们确定可能遇到了大量具有相同预排序前缀值的元组时，我们希望通过仅对未排序后缀键进行排序来优化元组排序。
 *
 * 问题是我们已经在另一个配置为按所有列排序的元组排序中累积了几个元组（假设可能有多个前缀键组）。因此，要切换到预排序前缀模式，我们必须回过头来查看我们已经累积的所有元组，以验证它们是否都是同一前缀键组的一部分，然后仅按未排序后缀键对它们进行排序。
 *
 * 虽然所有已获取的元组都很可能是单个前缀组的一部分，但我们还必须处理在大型前缀键组之前存在至少一个不同前缀键组的可能性。
 * ---------------------------------------------------------------- 
 */
static void fc_switchToPresortedPrefixMode(PlanState *fc_pstate)
{
	IncrementalSortState *fc_node = castNode(IncrementalSortState, fc_pstate);
	ScanDirection fc_dir;
	int64		fc_nTuples;
	TupleDesc	fc_tupDesc;
	PlanState  *fc_outerNode;
	IncrementalSort *fc_plannode = castNode(IncrementalSort, fc_node->ss.ps.plan);

	fc_dir = fc_node->ss.ps.state->es_direction;
	fc_outerNode = outerPlanState(fc_node);
	fc_tupDesc = ExecGetResultType(fc_outerNode);

	/* 首次配置前缀排序状态。 */
	if (fc_node->prefixsort_state == NULL)
	{
		Tuplesortstate *fc_prefixsort_state;
		int			fc_nPresortedCols = fc_plannode->nPresortedCols;

		/*
		 * 通过假设前缀列都是相等的来优化排序，因此我们只需要按任何剩余列排序。
		 */
		fc_prefixsort_state = tuplesort_begin_heap(fc_tupDesc,
												fc_plannode->sort.numCols - fc_nPresortedCols,
												&(fc_plannode->sort.sortColIdx[fc_nPresortedCols]),
												&(fc_plannode->sort.sortOperators[fc_nPresortedCols]),
												&(fc_plannode->sort.collations[fc_nPresortedCols]),
												&(fc_plannode->sort.nullsFirst[fc_nPresortedCols]),
												work_mem,
												NULL,
												fc_node->bounded ? TUPLESORT_ALLOWBOUNDED : TUPLESORT_NONE);
		fc_node->prefixsort_state = fc_prefixsort_state;
	}
	else
	{
		/* 下一个预排序数据组 */
		tuplesort_reset(fc_node->prefixsort_state);
	}

	/*
	 * 如果当前节点有边界，那么相当有可能大型前缀键组会受益于有界排序，因此配置元组排序以允许该优化。
	 */
	if (fc_node->bounded)
	{
		SO1_printf("Setting bound on presorted prefix tuplesort to: " INT64_FORMAT "\n",
				   fc_node->bound - fc_node->bound_Done);
		tuplesort_set_bound(fc_node->prefixsort_state,
							fc_node->bound - fc_node->bound_Done);
	}

	/*
	 * 尽可能多地从完整排序状态复制元组（即，在相同的前缀键组中）到前缀排序状态。
	 */
	for (fc_nTuples = 0; fc_nTuples < fc_node->n_fullsort_remaining; fc_nTuples++)
	{
		/*
		 * 当我们在完整排序的元组排序中遇到多个前缀键组时，我们必须将最后读取的元组带入下一个批次。
		 */
		if (fc_nTuples == 0 && !TupIsNull(fc_node->transfer_tuple))
		{
			tuplesort_puttupleslot(fc_node->prefixsort_state, fc_node->transfer_tuple);
			/* 带入的元组是我们新的组枢轴元组。 */
			ExecCopySlot(fc_node->group_pivot, fc_node->transfer_tuple);
		}
		else
		{
			tuplesort_gettupleslot(fc_node->fullsort_state,
								   ScanDirectionIsForward(fc_dir),
								   false, fc_node->transfer_tuple, NULL);

			/*
			 * 如果这是我们第一次循环，那么我们需要将获得的第一个元组保存为新的组枢轴。
			 */
			if (TupIsNull(fc_node->group_pivot))
				ExecCopySlot(fc_node->group_pivot, fc_node->transfer_tuple);

			if (fc_isCurrentGroup(fc_node, fc_node->group_pivot, fc_node->transfer_tuple))
			{
				tuplesort_puttupleslot(fc_node->prefixsort_state, fc_node->transfer_tuple);
			}
			else
			{
				/*
				 * 该元组不是当前批次的一部分，因此我们需要将其带入从完整排序元组排序传输到预排序前缀元组排序的下一个批次。我们实际没有必要做任何特殊的事情来保存这个元组，因为我们已经将其加载到node->transfer_tuple槽中，并且，即使该槽指向完整排序元组排序内部的内存，我们也不能重置该元组排序，直到我们完全转移出它的元组，因此这个引用是安全的。不过，我们确实需要重置组枢轴元组，因为我们已经完成了当前的前缀键组。
				 */
				ExecClearTuple(fc_node->group_pivot);

				/* 提前退出循环 */
				break;
			}
		}
	}

	/*
	 * 记录在完整排序批次中剩余的元组数量，以便我们知道在处理我们认为已遇到的大单一前缀键组中的剩余元组之前，是否需要对多个前缀键组进行排序。
	 */
	SO1_printf("Moving " INT64_FORMAT " tuples to presorted prefix tuplesort\n", fc_nTuples);
	fc_node->n_fullsort_remaining -= fc_nTuples;
	SO1_printf("Setting n_fullsort_remaining to " INT64_FORMAT "\n", fc_node->n_fullsort_remaining);

	if (fc_node->n_fullsort_remaining == 0)
	{
		/*
		 * 我们发现完整排序批次中的所有剩余元组都在同一个前缀键组中，并将所有这些元组移动到预排序前缀元组排序中。我们还不知道我们是否已经找到当前前缀键组中的最后一个元组，因此保存我们的枢轴比较元组，并继续从外部执行节点获取元组以加载到预排序前缀元组排序中。
		 */
		ExecCopySlot(fc_node->group_pivot, fc_node->transfer_tuple);
		SO_printf("Setting execution_status to INCSORT_LOADPREFIXSORT (switchToPresortedPrefixMode)\n");
		fc_node->execution_status = INCSORT_LOADPREFIXSORT;

		/*
		 * 确保清空传输元组槽，以便下次遇到大型前缀键组时，我们不会错误地假设我们有一个从前一个组带过来的元组。
		 */
		ExecClearTuple(fc_node->transfer_tuple);
	}
	else
	{
		/*
		 * 我们完成了一个组，但没有消耗掉完整排序状态中的所有元组，因此我们将对这个批次进行排序，让外部节点读取所有这些元组，然后再回过头来寻找另一个批次。
		 */
		SO1_printf("Sorting presorted prefix tuplesort with " INT64_FORMAT " tuples\n", fc_nTuples);
		tuplesort_performsort(fc_node->prefixsort_state);

		INSTRUMENT_SORT_GROUP(fc_node, prefixsort);

		if (fc_node->bounded)
		{
			/*
			 * 如果当前节点有边界并且我们已经排序了n个元组，那么剩余的功能边界是（原始边界 - n），因此保存当前处理的元组数，以便用于配置排序边界。
			 */
			SO2_printf("Changing bound_Done from " INT64_FORMAT " to " INT64_FORMAT "\n",
					   Min(fc_node->bound, fc_node->bound_Done + fc_nTuples), fc_node->bound_Done);
			fc_node->bound_Done = Min(fc_node->bound, fc_node->bound_Done + fc_nTuples);
		}

		SO_printf("Setting execution_status to INCSORT_READPREFIXSORT  (switchToPresortedPrefixMode)\n");
		fc_node->execution_status = INCSORT_READPREFIXSORT;
	}
}

/*
 * 使用元组排序对许多小组排序效率低下。为了解决这个问题，我们不会开始一个新组，直到当前组至少包含DEFAULT_MIN_GROUP_SIZE个元组（不幸的是，这也意味着我们不能假设小组的所有元组都有相同的前缀键）。当我们有一个小于DEFAULT_MIN_GROUP_SIZE的边界时，我们会在满足我们的边界后立即开始寻找新组，以避免获取超过我们绝对需要获取的元组数量。
 */
#define DEFAULT_MIN_GROUP_SIZE 32

/*
 * 虽然我们通过不在达到最小元组数量之前开始前缀键比较，从而为小前缀键组进行了优化，但我们不希望这种优化导致我们失去能够假设大型元组组完全按照前缀键预排序的好处。因此，我们使用DEFAULT_MAX_FULL_SORT_GROUP_SIZE截止值作为启发式方法，以确定何时我们认为已经遇到一个大组，如果我们在这一点上没有找到新的前缀键组，我们将过渡到预排序前缀键模式。
 */
#define DEFAULT_MAX_FULL_SORT_GROUP_SIZE (2 * DEFAULT_MIN_GROUP_SIZE)

/* ----------------------------------------------------------------
 *		ExecIncrementalSort
 *
 *		假设外部子树返回按目标排序列的某个前缀预排序的元组，执行增量排序。
 *
 *		条件：
 *		  -- 无。
 *
 *		初始状态：
 *		  -- 外部子节点准备好返回第一个元组。
 * ----------------------------------------------------------------
 */
static TupleTableSlot * fc_ExecIncrementalSort(PlanState *fc_pstate)
{
	IncrementalSortState *fc_node = castNode(IncrementalSortState, fc_pstate);
	EState	   *fc_estate;
	ScanDirection fc_dir;
	Tuplesortstate *fc_read_sortstate;
	Tuplesortstate *fc_fullsort_state;
	TupleTableSlot *fc_slot;
	IncrementalSort *fc_plannode = (IncrementalSort *) fc_node->ss.ps.plan;
	PlanState  *fc_outerNode;
	TupleDesc	fc_tupDesc;
	int64		fc_nTuples = 0;
	int64		fc_minGroupSize;

	CHECK_FOR_INTERRUPTS();

	fc_estate = fc_node->ss.ps.state;
	fc_dir = fc_estate->es_direction;
	fc_fullsort_state = fc_node->fullsort_state;

	/*
	 * 如果先前的迭代已经排序了一个批次，那么我们需要检查一下在该批次中是否还有剩余的元组可以返回，然后再进入其他执行状态。
	 */
	if (fc_node->execution_status == INCSORT_READFULLSORT
		|| fc_node->execution_status == INCSORT_READPREFIXSORT)
	{
		/*
		 * 如果可用，则从当前排序的组集返回下一个元组。
		 */
		fc_read_sortstate = fc_node->execution_status == INCSORT_READFULLSORT ?
			fc_fullsort_state : fc_node->prefixsort_state;
		fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;

		/*
		 * 我们必须在检查 outerNodeDone 之前从 tuplesort 填充槽，
		 * 因为如果没有更多元组，则会将槽设置为 NULL。
		 * 如果 tuplesort 是空的，但我们没有来自外部节点的可供排序的元组，
		 * 那么 outerNodeDone 将被设置，因此我们将返回那个现在为空的槽给调用者。
		 */
		if (tuplesort_gettupleslot(fc_read_sortstate, ScanDirectionIsForward(fc_dir),
								   false, fc_slot, NULL) || fc_node->outerNodeDone)

			/*
			 * 注意：没有一个好的测试用例可以直接测试 node->outerNodeDone 检查，
			 * 但我们需要它来处理任何计划，其中外部节点在尝试获取过多元组时会失败。
			 */
			return fc_slot;
		else if (fc_node->n_fullsort_remaining > 0)
		{
			/*
			 * 当我们过渡到预排序前缀模式时，我们可能已经在完整排序的 tuplesort 中
			 * 累积了至少一个额外的前缀键组。第一次调用 switchToPresortedPrefixMode()
			 * 将提取其中的第一个组，我们把这些元组返回给父节点，
			 * 但如果此时我们在完整排序状态中仍然有元组剩余（即 n_fullsort_remaining > 0），
			 * 那么我们需要重新执行前缀模式过渡函数来提取下一个前缀键组。
			 */
			SO1_printf("Re-calling switchToPresortedPrefixMode() because n_fullsort_remaining is > 0 (" INT64_FORMAT ")\n",
					   fc_node->n_fullsort_remaining);
			fc_switchToPresortedPrefixMode(fc_pstate);
		}
		else
		{
			/*
			 * 如果我们没有任何已排序的元组可供读取，并且我们当前没有
			 * 过渡到预排序前缀排序模式，那么是时候重新开始整个过程，
			 * 通过在完整排序状态中构建一个新组。
			 */
			SO_printf("Setting execution_status to INCSORT_LOADFULLSORT (n_fullsort_remaining > 0)\n");
			fc_node->execution_status = INCSORT_LOADFULLSORT;
		}
	}

	/*
	 * 在前向方向上扫描子计划，同时创建排序数据。
	 */
	fc_estate->es_direction = ForwardScanDirection;

	fc_outerNode = outerPlanState(fc_node);
	fc_tupDesc = ExecGetResultType(fc_outerNode);

	/* 将元组加载到完整排序状态中。 */
	if (fc_node->execution_status == INCSORT_LOADFULLSORT)
	{
		/*
		 * 初始化排序结构。
		 */
		if (fc_fullsort_state == NULL)
		{
			/*
			 * 为 isCurrentGroup() 初始化预排序列支持结构。 
			 * 在完整排序状态的初始初始化中执行此操作是正确的（而不是前缀排序状态），
			 * 因为我们总是首先加载完整排序状态。
			 */
			fc_preparePresortedCols(fc_node);

			/*
			 * 由于我们通过累积最少数量的元组来优化较小的前缀键组，因此我们不能假设
			 * 一组元组都有相同的前缀键值。因此，我们设置完整排序的 tuplesort
			 * 以按所有请求的排序键进行排序。
			 */
			fc_fullsort_state = tuplesort_begin_heap(fc_tupDesc,
												  fc_plannode->sort.numCols,
												  fc_plannode->sort.sortColIdx,
												  fc_plannode->sort.sortOperators,
												  fc_plannode->sort.collations,
												  fc_plannode->sort.nullsFirst,
												  work_mem,
												  NULL,
												  fc_node->bounded ?
												  TUPLESORT_ALLOWBOUNDED :
												  TUPLESORT_NONE);
			fc_node->fullsort_state = fc_fullsort_state;
		}
		else
		{
			/* 为下一个批次重置排序。 */
			tuplesort_reset(fc_fullsort_state);
		}

		
/*
		 * 计算剩余的元组，如果有界的话，配置有界排序和最小组大小。
		 */
		if (fc_node->bounded)
		{
			int64		fc_currentBound = fc_node->bound - fc_node->bound_Done;

			/*
			 * 对于完整排序模式，有界排序不太可能成为有效的优化，因为我们将完整排序模式限制在相对较小的元组数量，而且元组排序在达到(2 * bound)元组之前不会切换到top-n堆排序。
			 */
			if (fc_currentBound < DEFAULT_MIN_GROUP_SIZE)
				tuplesort_set_bound(fc_fullsort_state, fc_currentBound);

			fc_minGroupSize = Min(DEFAULT_MIN_GROUP_SIZE, fc_currentBound);
		}
		else
			fc_minGroupSize = DEFAULT_MIN_GROUP_SIZE;

		/*
		 * 因为我们必须读取下一个元组以找出我们遇到新的前缀键组，在后续组中，我们必须保留那个额外的元组并将其添加到新组的排序中，然后才从外部节点读取任何新元组。
		 */
		if (!TupIsNull(fc_node->group_pivot))
		{
			tuplesort_puttupleslot(fc_fullsort_state, fc_node->group_pivot);
			fc_nTuples++;

			/*
			 * 我们处于完整排序模式中，正在积累最小数量的元组，并且尚未检查前缀键的相等性，因此我们不能假设组的主元组将保持不变——除非我们使用的最小组大小为1，在这种情况下，主元组显然仍然是主元组。
			 */
			if (fc_nTuples != fc_minGroupSize)
				ExecClearTuple(fc_node->group_pivot);
		}


		/*
		 * 根据我们当前的操作模式，从外部节点尽可能多地提取元组。
		 */
		for (;;)
		{
			fc_slot = ExecProcNode(fc_outerNode);

			/*
			 * 如果外部节点无法提供更多元组，那么我们可以对当前组进行排序并返回这些元组。
			 */
			if (TupIsNull(fc_slot))
			{
				/*
				 * 我们需要稍后知道外部节点是否已经完成，以便能够区分批次完成和整个节点完成。
				 */
				fc_node->outerNodeDone = true;

				SO1_printf("Sorting fullsort with " INT64_FORMAT " tuples\n", fc_nTuples);
				tuplesort_performsort(fc_fullsort_state);

				INSTRUMENT_SORT_GROUP(fc_node, fullsort);

				SO_printf("Setting execution_status to INCSORT_READFULLSORT (final tuple)\n");
				fc_node->execution_status = INCSORT_READFULLSORT;
				break;
			}

			/* 累积下一组已排序的元组。 */
			if (fc_nTuples < fc_minGroupSize)
			{
				/*
				 * 如果我们尚未达到目标最小组大小，那么我们不需要检查当前前缀组中的包含性，因为此时我们将假设我们会对这一批进行完全排序，以避免大量非常小（因此效率低下）的排序。
				 */
				tuplesort_puttupleslot(fc_fullsort_state, fc_slot);
				fc_nTuples++;

				/*
				 * 如果我们已经达到了最小组大小，那么我们需要将最近的元组存储为基准。
				 */
				if (fc_nTuples == fc_minGroupSize)
					ExecCopySlot(fc_node->group_pivot, fc_slot);
			}
			else
			{
				/*
				 * 如果我们已经累积了足够的元组以达到最小组大小，那么我们需要将任何额外的元组与基准元组进行比较，以查看我们是否到达了该前缀键组的末尾。只有在找到更改的前缀键后，我们才能保证已经累积的元组的排序稳定性。
				 */
				if (fc_isCurrentGroup(fc_node, fc_node->group_pivot, fc_slot))
				{
					/*
					 * 只要前缀键与基准元组匹配，那么就将该元组加载到元组排序中。
					 */
					tuplesort_puttupleslot(fc_fullsort_state, fc_slot);
					fc_nTuples++;
				}
				else
				{
					/*
					 * 由于我们提取的元组不是当前前缀键组的一部分，我们不想将其作为当前批次的一部分进行排序。相反，我们使用 group_pivot 槽将其携带到下一批（尽管我们实际上不会将其视为组基准）。
					 */
					ExecCopySlot(fc_node->group_pivot, fc_slot);

					if (fc_node->bounded)
					{
						/*
						 * 如果当前节点有一个界限，并且我们已经排序了 n 个元组，则剩余的功能界限是（原始界限 - n），因此存储当前处理的元组数以便稍后用于配置排序状态的界限。
						 */
						SO2_printf("Changing bound_Done from " INT64_FORMAT " to " INT64_FORMAT "\n",
								   fc_node->bound_Done,
								   Min(fc_node->bound, fc_node->bound_Done + fc_nTuples));
						fc_node->bound_Done = Min(fc_node->bound, fc_node->bound_Done + fc_nTuples);
					}

					/*
					 * 一旦我们找到更改的前缀键，我们可以完成排序并过渡到读取已排序元组的模式。
					 */
					SO1_printf("Sorting fullsort tuplesort with " INT64_FORMAT " tuples\n",
							   fc_nTuples);
					tuplesort_performsort(fc_fullsort_state);

					INSTRUMENT_SORT_GROUP(fc_node, fullsort);

					SO_printf("Setting execution_status to INCSORT_READFULLSORT (found end of group)\n");
					fc_node->execution_status = INCSORT_READFULLSORT;
					break;
				}
			}

			/*
			 * 除非我们已经过渡到从完整排序状态读取，否则我们假设已经读取了至少 DEFAULT_MAX_FULL_SORT_GROUP_SIZE 个元组，这意味着我们很可能正在处理一组拥有相同前缀键的元组（但尚未找到该前缀键组中的最终元组），因此我们需要过渡到预排序前缀模式。
			 */
			if (fc_nTuples > DEFAULT_MAX_FULL_SORT_GROUP_SIZE &&
				fc_node->execution_status != INCSORT_READFULLSORT)
			{
				/*
				 * 我们存储的组基准已经被放入元组排序中；我们不想将其携带过来。由于我们尚未找到前缀键组的结束，似乎我们应该保留这个，但是我们实际上并不知道完整排序状态中可能代表多少个前缀键组，因此我们将让模式转移函数为我们管理这个状态。
				 */
				ExecClearTuple(fc_node->group_pivot);

				/*
				 * 不幸的是，元组排序 API 不包括检索元组的方法，除非执行了排序，因此即使我们可以依赖 FIFO 检索语义将它们传输到预排序前缀元组排序中，我们仍然执行排序。
				 */
				SO1_printf("Sorting fullsort tuplesort with " INT64_FORMAT " tuples\n", fc_nTuples);
				tuplesort_performsort(fc_fullsort_state);

				INSTRUMENT_SORT_GROUP(fc_node, fullsort);

				/*
				 * 如果完整排序的元组排序恰好切换到 top-n 堆排序模式，那么我们将只能检索 currentBound 元组（因为元组排序只保留了 top-n 元组）。即使我们尚未完成提取当前前缀键组，这也是安全的，因为我们“丢失”的元组已经被“排序”在保留的元组之下，而且我们已经在合同上保证不需要超过 currentBound 个元组。
				 */
				if (tuplesort_used_bound(fc_node->fullsort_state))
				{
					int64		fc_currentBound = fc_node->bound - fc_node->bound_Done;

					SO2_printf("Read " INT64_FORMAT " tuples, but setting to " INT64_FORMAT " because we used bounded sort\n",
							   fc_nTuples, Min(fc_currentBound, fc_nTuples));
					fc_nTuples = Min(fc_currentBound, fc_nTuples);
				}

				SO1_printf("Setting n_fullsort_remaining to " INT64_FORMAT " and calling switchToPresortedPrefixMode()\n",
						   fc_nTuples);

				/*
				 * 我们可能在完整排序状态中有多个前缀键组，因此模式转移函数需要知道它需要从完整排序过渡到预排序前缀排序。
				 */
				fc_node->n_fullsort_remaining = fc_nTuples;

				/* 将元组过渡到预排序前缀元组排序。 */
				fc_switchToPresortedPrefixMode(fc_pstate);

				/*
				 * 由于我们知道有元组需要移动到预排序前缀元组排序中，我们知道除非该过渡已验证所有元组属于同一前缀键组（在这种情况下我们可以直接继续加载元组到该元组排序中），否则我们应该在这里有一个元组返回。
				 *
				 * 无论如何，适当的执行状态应该已由 switchToPresortedPrefixMode() 设置，因此我们可以在这里退出循环，让适当的路径启动。
				 */
				break;
			}
		}
	}

	if (fc_node->execution_status == INCSORT_LOADPREFIXSORT)
	{
		
/*
		 * 我们只有在模式转换函数确认所有剩余的元组来自完全排序状态并且它们具有相同的前缀并将这些元组移动到前缀排序状态后，才会进入此状态。该函数还设置了一个组枢轴元组（不需要携带；它已经放入前缀排序状态）。
		 */
		Assert(!TupIsNull(fc_node->group_pivot));

		/*
		 * 从外部节点读取元组并将其加载到前缀排序状态，直到我们遇到一个前缀键与当前组枢轴元组不匹配的元组，因为在我们拥有所有匹配这些前缀键的元组之前，我们无法保证排序的稳定性。
		 */
		for (;;)
		{
			fc_slot = ExecProcNode(fc_outerNode);

			/*
			 * 如果我们已经耗尽了外部节点的元组，我们就完成了前缀排序状态的加载。
			 */
			if (TupIsNull(fc_slot))
			{
				/*
				 * 我们需要稍后知道外部节点是否已经完成，以便能够区分批次完成和整个节点完成。
				 */
				fc_node->outerNodeDone = true;
				break;
			}

			/*
			 * 如果元组的前缀键与我们的枢轴元组匹配，我们还没有完成，可以将其加载到前缀排序状态。如果不匹配，我们不想将其作为当前批次的一部分进行排序。相反，我们使用组枢轴槽将其携带到下一个批次（尽管我们实际上不会将其视为组枢轴）。
			 */
			if (fc_isCurrentGroup(fc_node, fc_node->group_pivot, fc_slot))
			{
				tuplesort_puttupleslot(fc_node->prefixsort_state, fc_slot);
				fc_nTuples++;
			}
			else
			{
				ExecCopySlot(fc_node->group_pivot, fc_slot);
				break;
			}
		}

		/*
		 * 执行排序并开始将元组返回给父计划节点。
		 */
		SO1_printf("Sorting presorted prefix tuplesort with " INT64_FORMAT " tuples\n", fc_nTuples);
		tuplesort_performsort(fc_node->prefixsort_state);

		INSTRUMENT_SORT_GROUP(fc_node, prefixsort);

		SO_printf("Setting execution_status to INCSORT_READPREFIXSORT (found end of group)\n");
		fc_node->execution_status = INCSORT_READPREFIXSORT;

		if (fc_node->bounded)
		{
			/*
			 * 如果当前节点有边界，并且我们已经排序了 n 个元组，则剩余的功能边界是（原始边界 - n），因此存储当前处理的元组数量以用于配置排序边界。
			 */
			SO2_printf("Changing bound_Done from " INT64_FORMAT " to " INT64_FORMAT "\n",
					   fc_node->bound_Done,
					   Min(fc_node->bound, fc_node->bound_Done + fc_nTuples));
			fc_node->bound_Done = Min(fc_node->bound, fc_node->bound_Done + fc_nTuples);
		}
	}

	/* 恢复到用户指定的方向。 */
	fc_estate->es_direction = fc_dir;

	/*
	 * 从 tuplesort 获取第一个或下一个元组。如果没有更多元组，则返回 NULL。
	 */
	fc_read_sortstate = fc_node->execution_status == INCSORT_READFULLSORT ?
		fc_fullsort_state : fc_node->prefixsort_state;
	fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;
	(void) tuplesort_gettupleslot(fc_read_sortstate, ScanDirectionIsForward(fc_dir),
								  false, fc_slot, NULL);
	return fc_slot;
}

/* ----------------------------------------------------------------
 *		ExecInitIncrementalSort
 *
 *		创建排序节点的运行时状态信息，该节点由规划器生成并初始化其外部子树。
 * ----------------------------------------------------------------
 */
IncrementalSortState *
ExecInitIncrementalSort(IncrementalSort *fc_node, EState *fc_estate, int fc_eflags)
{
	IncrementalSortState *fc_incrsortstate;

	SO_printf("ExecInitIncrementalSort: initializing sort node\n");

	/*
	 * 增量排序不能与 EXEC_FLAG_BACKWARD 或 EXEC_FLAG_MARK 一起使用，因为当前排序状态仅包含一个排序批次，而不是完整的结果集。
	 */
	Assert((fc_eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)) == 0);

	/* 初始化状态结构。 */
	fc_incrsortstate = makeNode(IncrementalSortState);
	fc_incrsortstate->ss.ps.plan = (Plan *) fc_node;
	fc_incrsortstate->ss.ps.state = fc_estate;
	fc_incrsortstate->ss.ps.ExecProcNode = fc_ExecIncrementalSort;

	fc_incrsortstate->execution_status = INCSORT_LOADFULLSORT;
	fc_incrsortstate->bounded = false;
	fc_incrsortstate->outerNodeDone = false;
	fc_incrsortstate->bound_Done = 0;
	fc_incrsortstate->fullsort_state = NULL;
	fc_incrsortstate->prefixsort_state = NULL;
	fc_incrsortstate->group_pivot = NULL;
	fc_incrsortstate->transfer_tuple = NULL;
	fc_incrsortstate->n_fullsort_remaining = 0;
	fc_incrsortstate->presorted_keys = NULL;

	if (fc_incrsortstate->ss.ps.instrument != NULL)
	{
		IncrementalSortGroupInfo *fc_fullsortGroupInfo =
		&fc_incrsortstate->incsort_info.fullsortGroupInfo;
		IncrementalSortGroupInfo *fc_prefixsortGroupInfo =
		&fc_incrsortstate->incsort_info.prefixsortGroupInfo;

		fc_fullsortGroupInfo->groupCount = 0;
		fc_fullsortGroupInfo->maxDiskSpaceUsed = 0;
		fc_fullsortGroupInfo->totalDiskSpaceUsed = 0;
		fc_fullsortGroupInfo->maxMemorySpaceUsed = 0;
		fc_fullsortGroupInfo->totalMemorySpaceUsed = 0;
		fc_fullsortGroupInfo->sortMethods = 0;
		fc_prefixsortGroupInfo->groupCount = 0;
		fc_prefixsortGroupInfo->maxDiskSpaceUsed = 0;
		fc_prefixsortGroupInfo->totalDiskSpaceUsed = 0;
		fc_prefixsortGroupInfo->maxMemorySpaceUsed = 0;
		fc_prefixsortGroupInfo->totalMemorySpaceUsed = 0;
		fc_prefixsortGroupInfo->sortMethods = 0;
	}

	/*
	 * 杂项初始化
	 *
	 * 排序节点不初始化它们的 ExprContexts，因为它们从不调用 ExecQual 或 ExecProject。
	 */

	/*
	 * 初始化子节点。
	 *
	 * 增量排序不支持反向扫描和标记/恢复，因此我们在这里不打算移除 eflags 中的标志。我们允许传递一个
	 * REWIND 标志，因为虽然增量排序无法使用它，子节点可能能够做一些更有用的事情。
	 */
	outerPlanState(fc_incrsortstate) = ExecInitNode(outerPlan(fc_node), fc_estate, fc_eflags);

	/*
	 * 初始化扫描槽和类型。
	 */
	ExecCreateScanSlotFromOuterPlan(fc_estate, &fc_incrsortstate->ss, &TTSOpsMinimalTuple);

	/*
	 * 初始化返回槽和类型。无需初始化投影信息，因为我们不做任何投影。
	 */
	ExecInitResultTupleSlotTL(&fc_incrsortstate->ss.ps, &TTSOpsMinimalTuple);
	fc_incrsortstate->ss.ps.ps_ProjInfo = NULL;

	/*
	 * 初始化独立槽以存储用于枢轴前缀键的元组和用于将元组从一个批次传递到下一个批次。
	 */
	fc_incrsortstate->group_pivot =
		MakeSingleTupleTableSlot(ExecGetResultType(outerPlanState(fc_incrsortstate)),
								 &TTSOpsMinimalTuple);
	fc_incrsortstate->transfer_tuple =
		MakeSingleTupleTableSlot(ExecGetResultType(outerPlanState(fc_incrsortstate)),
								 &TTSOpsMinimalTuple);

	SO_printf("ExecInitIncrementalSort: sort node initialized\n");

	return fc_incrsortstate;
}

/* ----------------------------------------------------------------
 *		ExecEndIncrementalSort(node)
 * ----------------------------------------------------------------
 */
void ExecEndIncrementalSort(IncrementalSortState *fc_node)
{
	SO_printf("ExecEndIncrementalSort: shutting down sort node\n");

	/* 清除扫描元组 */
	ExecClearTuple(fc_node->ss.ss_ScanTupleSlot);
	/* 必须删除对排序结果元组的指针 */
	ExecClearTuple(fc_node->ss.ps.ps_ResultTupleSlot);
	/* 必须从外部节点删除独立元组槽 */
	ExecDropSingleTupleTableSlot(fc_node->group_pivot);
	ExecDropSingleTupleTableSlot(fc_node->transfer_tuple);

	/*
	 * 释放 tuplesort 资源。
	 */
	if (fc_node->fullsort_state != NULL)
	{
		tuplesort_end(fc_node->fullsort_state);
		fc_node->fullsort_state = NULL;
	}
	if (fc_node->prefixsort_state != NULL)
	{
		tuplesort_end(fc_node->prefixsort_state);
		fc_node->prefixsort_state = NULL;
	}

	/*
	 * 关闭子计划。
	 */
	ExecEndNode(outerPlanState(fc_node));

	SO_printf("ExecEndIncrementalSort: sort node shutdown\n");
}

void ExecReScanIncrementalSort(IncrementalSortState *fc_node)
{
	PlanState  *fc_outerPlan = outerPlanState(fc_node);

	/*
	 * 增量排序即使在参数没有变化（例如，回退）的情况下也不支持高效的重新扫描，因为与常规排序不同，
	 * 我们不会一次性存储所有元组以进行完整排序。
	 *
	 * 因此，即使设置了 EXEC_FLAG_REWIND，我们也只是重置我们所有的状态，并重新执行排序以及子节点。
	 * 增量排序本身无法做任何更智能的事情，但也许子节点可以。
	 *
	 * 理论上，如果我们只用一个批次填充了完整排序（并且尚未重置为新批次），那么我们可以有效地回退，
	 * 但这似乎是一个狭窄的情况，因此目前没有特别处理的价值。
	 */

	/* 必须删除对排序结果元组的指针 */
	ExecClearTuple(fc_node->ss.ps.ps_ResultTupleSlot);

	if (fc_node->group_pivot != NULL)
		ExecClearTuple(fc_node->group_pivot);
	if (fc_node->transfer_tuple != NULL)
		ExecClearTuple(fc_node->transfer_tuple);

	fc_node->outerNodeDone = false;
	fc_node->n_fullsort_remaining = 0;
	fc_node->bound_Done = 0;

	fc_node->execution_status = INCSORT_LOADFULLSORT;

	/*
	 * 如果我们已经设置了任一排序状态，则需要重置它们。
	 * 我们可以结束它们并将指针置为 null，但没有理由重新支付设置成本，并且由于 ExecIncrementalSort
	 * 通过检查完整排序状态是否已初始化来保护已排序列函数，因此在这里将排序状态设置为 null 可能
	 * 实际上会导致内存泄漏。
	 */
	if (fc_node->fullsort_state != NULL)
		tuplesort_reset(fc_node->fullsort_state);
	if (fc_node->prefixsort_state != NULL)
		tuplesort_reset(fc_node->prefixsort_state);

	/*
	 * 如果子节点的 chgParam 不为 null，则计划将在第一个 ExecProcNode 中重新扫描。
	 */
	if (fc_outerPlan->chgParam == NULL)
		ExecReScan(fc_outerPlan);
}

/* ----------------------------------------------------------------
 *						并行查询支持
 * ----------------------------------------------------------------
 */

/* ----------------------------------------------------------------
 *		ExecSortEstimate
 *
 *		估算传播排序统计信息所需的空间。
 * ----------------------------------------------------------------
 */
void ExecIncrementalSortEstimate(IncrementalSortState *fc_node, ParallelContext *fc_pcxt)
{
	Size		fc_size;

	/* 如果没有工具监控或没有工作程序，则不需要此 */
	if (!fc_node->ss.ps.instrument || fc_pcxt->nworkers == 0)
		return;

	fc_size = mul_size(fc_pcxt->nworkers, sizeof(IncrementalSortInfo));
	fc_size = add_size(fc_size, offsetof(SharedIncrementalSortInfo, sinfo));
	shm_toc_estimate_chunk(&fc_pcxt->estimator, fc_size);
	shm_toc_estimate_keys(&fc_pcxt->estimator, 1);
}

/* ----------------------------------------------------------------
 *		ExecSortInitializeDSM
 *
 *		为排序统计信息初始化 DSM 空间。
 * ----------------------------------------------------------------
 */
void ExecIncrementalSortInitializeDSM(IncrementalSortState *fc_node, ParallelContext *fc_pcxt)
{
	Size		fc_size;

	/* 如果没有工具监控或没有工作程序，则不需要此 */
	if (!fc_node->ss.ps.instrument || fc_pcxt->nworkers == 0)
		return;

	fc_size = offsetof(SharedIncrementalSortInfo, sinfo)
		+ fc_pcxt->nworkers * sizeof(IncrementalSortInfo);
	fc_node->shared_info = shm_toc_allocate(fc_pcxt->toc, fc_size);
	
/* 确保任何未填充的槽将包含零 */
	memset(fc_node->shared_info, 0, fc_size);
	fc_node->shared_info->num_workers = fc_pcxt->nworkers;
	shm_toc_insert(fc_pcxt->toc, fc_node->ss.ps.plan->plan_node_id,
				   fc_node->shared_info);
}

/* ----------------------------------------------------------------
 *		ExecSortInitializeWorker
 *
 *		将工作线程附加到用于排序统计信息的 DSM 空间。
 * ----------------------------------------------------------------
 */
void ExecIncrementalSortInitializeWorker(IncrementalSortState *fc_node, ParallelWorkerContext *fc_pwcxt)
{
	fc_node->shared_info =
		shm_toc_lookup(fc_pwcxt->toc, fc_node->ss.ps.plan->plan_node_id, true);
	fc_node->am_worker = true;
}

/* ----------------------------------------------------------------
 *		ExecSortRetrieveInstrumentation
 *
 *		将排序统计信息从 DSM 转移到私有内存。
 * ----------------------------------------------------------------
 */
void ExecIncrementalSortRetrieveInstrumentation(IncrementalSortState *fc_node)
{
	Size		fc_size;
	SharedIncrementalSortInfo *fc_si;

	if (fc_node->shared_info == NULL)
		return;

	fc_size = offsetof(SharedIncrementalSortInfo, sinfo)
		+ fc_node->shared_info->num_workers * sizeof(IncrementalSortInfo);
	fc_si = palloc(fc_size);
	memcpy(fc_si, fc_node->shared_info, fc_size);
	fc_node->shared_info = fc_si;
}
